1. Field of the Invention
The present invention relates to an image processing method and apparatus and, more particularly, to an image compression method and apparatus for compressing image data by switching a compression method between a reversible compression method and an irreversible compression method in accordance with the type of image, and a data expansion method and apparatus for expanding data including both reversibly compressed data and irreversibly compressed data.
2. Description of the Related Art
In recent years, with spread of, e.g., DTP, images to be created on computers are required to have high image quality, and tend to have a large number of colors and gradation levels.
The information amount of an image of this type is as large as about 46 Mbytes in the case of, e.g., an A4 size, 400 dpi, 256 gradation levels, and three primary colors. The information amount can be decreased if image data is processed as code information of, e.g., a page description language (to be abbreviated to as "PDL" hereinafter). In this case, however, development from code information to image data requires a long period of time, and original code data having a smaller information amount cannot be generated from developed image data. For this reason, the compression technique of image data is important.
As a general compression method of a color multi-value image, an ADCT (Adaptive Discrete Cosine Transform) method recommended by the JPEG (Joint Photographic Experts Group) is known. The ADCT image compression method will be described below.
FIG. 14 is a block diagram showing an arrangement of an ADCT image compression apparatus.
Referring to FIG. 14, reference numeral 3101 denotes a color conversion section for converting an RGB color space of the NTSC system into a YCrCb color space expressed by a luminance signal Y and two color difference signals Cr and Cb.
Reference numeral 3102 denotes a sub sampling section for decreasing color difference data by utilizing the characteristics that human eyes are sensitive to luminance but insensitive to color differences. More specifically, the section 3102 calculates an average value of two adjacent color difference data to decrease the color difference data amount to 1/2.
Reference numeral 3103 denotes a DCT section for dividing image data output from the sub sampling section 3102 into blocks each consisting of 8.times.8 pixels, which blocks form a matrix in the horizontal and vertical directions, and executing DCT (Discrete Cosine Transform) to convert the blocks into frequency space data.
Reference numeral 3104 denotes a quantization section for dividing 8.times.8=64 DCT coefficients respectively with quantization values having different step widths to convert them into quantization data.
Reference numeral 3105 denotes a Huffman encoding section for classifying 64 quantized DCT coefficients output from the quantization section 3104 into one DC coefficient and 64 AC coefficients, and encoding these coefficients in accordance with a Huffman table recommended by the JPEG. The encoded data are added with header information such as quantization table data, Huffman table data, and the like, and are then stored in a memory or transmitted to another apparatus.
FIG. 15 is a block diagram showing an arrangement of an ADCT data expansion apparatus.
Referring to FIG. 15, reference numeral 3205 denotes a Huffman decoding section for decoding input encoded data into quantized data.
Reference numeral 3204 denotes an inverse quantization section for converting quantized data output from the Huffman decoding section 3205 into DCT coefficient data. The inverse quantization is achieved by multiplying 64 coefficients with the corresponding quantization values using the quantization table used upon quantization in the quantization section 3104 in FIG. 14.
Reference numeral 3203 denotes an inverse DCT section for executing inverse DCT of DCT coefficient data output from the inverse quantization section 3204 to convert them into actual image data.
Reference numeral 3202 denotes an interpolation section for interpolating Cr and Cb data omitted from the image data output from the inverse DCT section 3203 by a simple repetition method. Note that omission of Cr and Cb data occurs when data is compressed by the sub sampling section 3102 in FIG. 14.
Reference numeral 3201 denotes a color conversion section for converting YCrCb color space data output from the interpolation section 3202 into NTSC-RGB color space data or color space data corresponding to the device.
The processing flow of the ADCT image compression apparatus will be described below by taking actual data as an example.
FIG. 16 shows NTSC-RGB color space data as a portion of color multi-value image data created by a computer, i.e., a portion (16.times.16 pixels) of image data in which a character portion of a color multi-value image is developed.
Referring to FIG. 16, reference numeral 3301 denotes R data; 3302, G data; and 3303, B data. Note that each pixel has a data range of 8 bits (0 to 255), and in FIG. 16, a portion of a character in blue expressed by (R, G, B)=(30, 30, 225) is drawn on a relatively dark white background expressed by (R, G, B)=(225, 225, 225).
The color conversion section 3101 executes conversion from an NTSC-RGB color space into a YCrCb color space using the following equations: EQU Y=0.299.times.R+0.587.times.G+0.114.times.B EQU Cr=0.713(R-Y) EQU Cb=0.564(B-Y)
Furthermore, in order to allow overshoot and undershoot in calculations in the YCrCb color space according to the CCIR recommendation, the section 3101 rounds the data using the following equations: EQU Y=219.0.times.Y+16.5 EQU Cr=224.0.times.Cr+128.5 EQU Cb=224.0.times.Cb+128.5
The sub sampling section 3102 performs sub sampling of Cr and Cb data obtained by the above-mentioned equations. As a sub sampling method, a simple thinning method, a MAX data selection method, a MIN data selection method, and the like are known. In this case, an average value method is used. More specifically, with the average value method, an average value of two adjacent pixel data is used as one data.
FIG. 17 shows the processing results of the image data shown in FIG. 16 by the color conversion section 3101 and the sub sampling section 3102. Referring to FIG. 17, reference numeral 3401 denotes Y data; 3402, Cr data; and 3403, Cb data. The data amounts of the Cr and Cb data are reduced to 1/2 by the sub sampling processing.
The Y, Cr, and Cb data shown in FIG. 17 are input to the DCT section 3103. The DCT section 3103 divides the input data into 8.times.8 data blocks forming a matrix in the horizontal and vertical directions. As a result of block division, the Y data 3401 is divided into four blocks 3401a to 3401d, as shown in FIG. 17. Similarly, the Cr data 3402 is divided into two blocks 3402a and 3402b, and the Cb data 3403 is divided into two blocks 3403a and 3403b. Subsequently, the DCT section 3103 executes DCT for these eight blocks.
FIG. 18 shows the DCT result of the eight blocks shown in FIG. 17.
Referring to FIG. 18, reference numeral 3501 denotes DCT coefficients of the Y data. Blocks 3501a to 3501d respectively correspond to blocks 3401a to 3401d shown in FIG. 17. Similarly, reference numeral 3502 denotes DCT coefficients of the Cr data; and 3503, DCT coefficients of the Cb data. Note that each block after DCT consists of one DC component at the upper left corner, and remaining 63 AC components.
The DCT coefficient data 3501 to 3503 shown in FIG. 18 are quantized by the quantization section 3104. In this case, quantization is performed based on quantization tables recommended by the JPEG.
FIG. 19 shows quantization tables used in quantization. Referring to FIG. 19, reference numeral 4001 denotes a quantization table for Y components; and 4002, a quantization table for Cr and Cb components.
FIG. 20 shows the quantization result of DCT coefficient data shown in FIG. 18 using the quantization tables shown in FIG. 19. Referring to FIG. 20, reference numeral 3601 denotes quantized data of the Y components; 3602, quantized data of the Cr components; and 3603, quantized data of the Cb components.
The encoding section 3105 classifies the quantized data 3601 to 3603 shown in FIG. 20 into DC and AC components. As for the DC components, the section 3105 forms an optimal Huffman encoding table on the basis of a histogram of a difference from a DC component of the previous block, and performs encoding according to the table. As for the AC components, the section 3105 sorts the AC components in a zigzag order shown in FIG. 21, forms an optimal Huffman encoding table on the basis of a histogram of a combination of a run length of coefficients 0 (the number of coefficients 0 until a coefficient x other than 0 appears), and the value x, and performs encoding according to the table.
Since each pixel has a range of 8 bits, original 16.times.16 pixel data in the NTSC-RGB color space, which has a data amount of 6,144 bits (=16.times.16.times.three colors.times.8 bits), is compressed to 795 bits when the data is output from the encoding section 3105. Therefore, image data is compressed to about 1/7.7 (6,144/795.apprxeq.7.7). However, in practice, since image size data, quantization table data, encoding table data, and the like are added to the data encoded by the encoding section 3105, the compression ratio is slightly lowered.
The processing flow of the ADCT data expansion apparatus will be described below.
The Huffman decoding section 3205 decodes input encoded data.
The inverse quantization section 3204 multiplies quantized data output from the Huffman decoding section 3205 with the coefficients of the quantization tables shown in FIG. 19, thereby executing inverse quantization.
With the above-mentioned processing, data shown in FIG. 22 are obtained. FIG. 22 shows the result of Huffman decoding and inverse quantization of the ADCT-compressed image data. Reference numeral 3701 denotes Y components; 3702, Cr components; and 3703, Cb components.
As can be seen from a comparison between the inverse-quantized data (DCT coefficient data) shown in FIG. 22 and the DCT coefficient data before quantization shown in FIG. 18, these two data are apparently different from each other.
Subsequently, the inverse DCT section 3203 executes inverse DCT of the DCT coefficient data output from the inverse quantization section 3204 to reconvert them into Y, Cr, and Cb data. FIG. 23 shows the inverse DCT result of the DCT coefficient data shown in FIG. 22 by the inverse DCT section 3203. Reference numeral 3801 denotes Y data; 3802, Cr data; and 3803, Cb data.
The interpolation section 3202 interpolates data omitted from the image data output from the inverse DCT section 3203, and the color conversion section 3201 converts the YCrCb color space data output from the interpolation section 3202 into NTSC-RGB color space data.
FIG. 24 shows data finally obtained by the ADCT data expansion apparatus. Reference numeral 3901 denotes R data; 3902, G data; and 3903, B data.
However, the above-mentioned tech nique suffers from the following problems.
More specifically, the ADCT image compression method is an irreversible compression method which loses data upon sub sampling and quantization. Therefore, as can be apparent from a comparison between NTSC-RGB color space data (FIG. 16) before compression, and NTSC-RGB space data (FIG. 24) as a result of compression and expansion of the data of FIG. 16, data expanded by the ADCT image compression method becomes different from data before compression. In other words, image quality deteriorates.
The merits of an image created on a computer (computer-created image) are a smooth outline, noise-free color painting based on a single color per figure (or character), and the like. However, when image data is compressed and expanded by the ADCT image compression method, a non-smooth outline of a figure, pseudo edge called mosquito noise, coloring due to quantization, and the like occur, and the merits of the computer-created image cannot be fully exhibited. Especially, since the above-mentioned compression method performs 8.times.8 block processing, a considerable change in color occurs at the boundary areas of the blocks.
When the compression ratio is to be increased in the ADCT image compression method, the AC components of the DCT coefficients are finally lost, and a block distortion is generated. In the extreme case, the resolution may deteriorate to, e.g., 1/8.
For this reason, compression may be performed while suppressing quantization so as not to cause conspicuous deterioration of image quality. However, such a technique is not practical in terms of the compression ratio since a computer-created image is originally characterized by many high-frequency data. Therefore, a computer-created image such as an image created by DTP need be compressed by a reversible method capable of obtaining a high compression ratio.
As a compression method for a color multi-value image created by a computer, methods shown in FIGS. 25 and 26 are known.
In the compression method shown in FIG. 25, a run length identification circuit 4012 identifies the run length of pixel data having the same color, and an encoding section 4013 encodes and transmits the run length of the color and pixel data at that time. That is, the concept of a so-called MH encoding method is extended to color image encoding.
In the compression method shown in FIG. 26, a line memory 4102 for storing previous line data is arranged, a run length identification circuit 4103 identifies the run length of pixel data having the same color, and an encoding section 4104 encodes and transmits the run length of the color and pixel data at that time with reference to previous line information. That is, the concept of a so-called MR encoding method is extended to color image encoding.
Each of the above-mentioned methods can obtain a very high compression ratio when pixel data having the same value continuously appear for a long period of time. However, these methods are not suitable for an image including fine patterns such as a DTP image. Also, since the encoding section often uses Huffman encoding, and the like, the circuit is complicated. In addition, since the run length identification circuit is required, encoding cannot be started until the run length ends, thus disturbing real-time processing.
Furthermore, the compression method shown in FIG. 26 aims at a higher compression ratio than the compression ratio shown in FIG. 25 by utilizing two-dimensional correlation of an image. However, the method shown in FIG. 26 must have a pixel data memory for at least one line.
In a method of compressing image data by a reversible compression method such as Huffman encoding, the data amount changes after compression. In particular, when a gradation image or a natural image read by an image scanner is reversibly compressed, the compressed data may often have an extremely large data amount. For this reason, a large-capacity image memory for the worst case must be prepared.